1. Field
The disclosed subject matter relates generally to methods for location determination, and more particularly to methods using various heuristics techniques for resolving ambiguity in location determination in environments with or without noise.
2. Background
In range-based location determination systems, measurements of ranging signals from a plurality of sources are converted to distance information associated with the source of each ranging signal. Distances to different sources with known locations are combined to solve for the unknown user location via geometric techniques known, for example as trilateration (a.k.a. triangulation). If delay of ranging signals cannot be known reliably (e.g. in asynchronous systems where the user clock is not synchronized to the network), location determination algorithms may treat user clock temporal bias as another unknown, to be solved for by the trilateration process, using an additional measurement.
However, a location determination system is ambiguous if more than one location determination solution set of user coordinates and clock temporal bias is consistent with a set of distance measurements. Location determination systems can produce ambiguous location determination solutions in three distinct ways: first, ambiguity can be caused by insufficient measurements; second, ambiguity may be introduced by the properties of the algorithm employed in location determination; and third, ambiguity may be introduced by the presence of noisy measurements.
First, a system has an insufficient number of measurements when the number of unknowns is greater than or equal to the number of independent measurements. For example, consider the case where the unknowns are the two-dimensional user spatial coordinates and user clock temporal bias. Consider the case depicted in FIG. 1. There are three unknowns, namely the mobile station latitude, longitude and clock temporal bias. There are three base stations, namely BS1, BS2 and BS3, and three associated distance measurements. Circles are plotted centered at a particular base station, with radii given by the sum of the distance between the mobile station and the base station as measured at the mobile station, and the computed clock temporal bias corresponding to a fitting solution. Given three independent distance measurements, there are two possible location determination solutions, depicted at the intersection of each set of circles.
Second, the nature of the algorithm used for locating a user can also be a source of ambiguity. A well known algorithm that is susceptible to ambiguity is described in the U.S. Pat. No. 6,289,280. This algorithm solves for unknowns using a closed form system of equations. Because it solves for the user location algebraically, this algorithm runs efficiently, making it suitable to applications and devices with time or resource constraints. The solution uses linear algebra manipulations to combine the measurements into a system of quadratic equations where the number of equations equals the number of unknowns. Two solutions are produced associated with the two roots of the quadratic equations. The two solutions form an ambiguous set of solutions which needs to be resolved by additional means.
For example, consider the case where the unknowns are the two-dimensional user spatial coordinates and user clock temporal bias. With four measurements, the system can be said to have a sufficient number of measurements to unambiguously solve for the user location. Yet, when the algebraic method is used, the four measurements are combined into three “average” measurements and two solutions corresponding to these averages are identified, as shown in FIG. 2.
Third, noisy measurements can lead to error in the determination of user location. Consider a method for location determination in noisy environments by assuming the noise to be a discrete variable with known or computable statistical parameters. A set of adjusted measurements and corresponding solution are generated for each assumed noise level. Such location determination system is ambiguous, thus also warranting ambiguity resolution techniques. For example, in FIG. 3, consider three noise levels, each 100 meters apart, associated with the measurement from base station BS2. For each noise level, a set of circles is plotted as before, with a radius corresponding to the sum of distance measurement (in the case of BS2, this measurement is adjusted by the assumed noise level) and the clock temporal bias computed. There are three ambiguous solutions, associated with each noise level, shown by the intersection of circles.
Accordingly, since more than one possible solution is presented by these prior art algorithms, it would be desirable to provide a method for selecting the correct (a.k.a. final) location determination solution from a set of ambiguous location determination solutions.